<?php
/**
 * User: LRZ
 * Date: 2020/2/22
 * Time: 12:23
 */

/**
 *  949.给定数字能组成的最大时间
 *
 *  标签：数学
 *
 *  给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。
 *  最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算起，过得越久，时间越大。
 *  以长度为 5 的字符串返回答案。如果不能确定有效时间，则返回空字符串。
 *
 *  示例 1：
 *      输入：[1,2,3,4]
 *      输出："23:41"
 *
 *  示例 2：
 *      输入：[5,5,5,5]
 *      输出：""
 *   
 *  提示：
 *      A.length == 4
 *      0 <= A[i] <= 9
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/largest-time-for-given-digits
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$A   = [0, 0, 0, 0];
$res = largestTimeFromDigits($A);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function largestTimeFromDigits($A)
{
    $res = -1;
    for ($i = 0; $i < 4; $i++) {
        for ($j = 0; $j < 4; $j++) {
            if ($j !== $i) {
                for ($k = 0; $k < 4; $k++) {
                    if ($k !== $i && $k !== $j) {
                        $l     = 6 - $i - $j - $k;
                        $hours = 10 * $A[$i] + $A[$j];
                        $min   = 10 * $A[$k] + $A[$l];
                        if ($hours < 24 && $min < 60) {
                            $res = max($res, $hours * 60 + $min);
                        }
                    }
                }
            }
        }
    }
    return $res >= 0 ? sprintf('%02d:%02d', $res / 60, $res % 60) : '';
}